package com.liu.algorithm.search.binary;

/**
 * 给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
 *
 * 有序数组+搜索值 = 二分查找
 */
public class Leetcode35 {
    public static void main(String[] args) {
        Leetcode35 obj = new Leetcode35();
        int[] nums = {-1, 0, 5};
        int target = 1;
        System.out.println(obj.searchInsert(nums, target));
    }
    public int searchInsert(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        while (left <= right) {
            int index = (left + right) / 2;
            if (target < nums[index]) {
                right = index - 1;
            }
            else if (target > nums[index]) {
                left = index + 1;
            }
            else {
                return index;
            }
        }
        return left;
    }
}
